﻿#pragma once
#include<vector>

// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>//这是对前面模板HashFunc的string特化类型
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;//防止abcd与dcba的ASCII码值之和相同
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE

	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))//如果以前插入过相同键值
			{
				return false;
			}

			if ((_n * 10) / _tables.size() >= 7)//扩容
			{
				HashTable<K, V, Hash>newh;
				newh._tables.resize(2 * _tables.size());

				for (int i = 0; i < _tables.size(); ++i)
				{
					if (_tables[i]._state == EXIST)
					{
						newh.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newh._tables);
			}

			Hash h;

			size_t index = h(kv.first) % _tables.size();//确定插入下标
			while (_tables[index]._state == EXIST)
			{
				++index;
				index = index % _tables.size();
			}
			_tables[index]._state = EXIST;
			_tables[index]._kv = kv;
			++_n;
			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash h;
			size_t index = h(key) % _tables.size();//确定查找下标


			while (_tables[index]._state != EMPTY)
			{
				if ( key == _tables[index]._kv.first)
				{
					return &_tables[index];
				}
				++index;
				index %= _tables.size();
			}

			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = find(key);
			if (ret)
			{
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};
}
